Базовые понятия о графах

Графом $G = (V, E)$ называется упорядоченная пара, где $V$ — множество вершин, а $E$ — мультиотношение на множестве $V$, называемое множеством ребер. Если $E$ — симметрично ($v_i v_j \in E \Rightarrow v_j v_i \in E$), то граф неориентированный и стрелки не рисуются.

Матрица отношения $E$ называется **матрицей смежности** графа.

У каждой вершин $v$ есть **входящая степень** $\deg^{+}(v)$ ($d^{+}(v)$) и **исходящая** $\deg^{-}(v)$ ($d^{-}(v)$).

**Обыкновенный граф** — неориентированный граф без петель и кратных ребер.

$K_n$ — **полный граф** на $n$ вершинах или $n$-**клика**.

$O_n$ — граф без ребер на $n$ вершинах.